package com.mlh.dp.old;

// 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

// 输入: prices = [1,2,3,0,2]
// 输出: 3
// 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]


//未解出

//题解
// 状态定义
// 我们定义dp[i][j]为：第iii天的选择持股或者不持股，所能获取获得的最大利润。我们用j=0表示持股，j=1表示不持股。
//
// 那么我们可以得出，dp[i][0]可以由两种前驱状态转移而来：
//
// 第i−1天就已经持有股票了，第i天什么也不需要做
// 第i−1天没有股票，但是第i−1天没有卖出股票。因为如果昨天卖出了，今天就不能买了。
// 这就有问题了，dp[i−1][1]只能表示第i−1没有股票，但不知道是在第i−1天卖出的股票还是之前卖出的股票。
//
// 所以我们需要将不持股不持股不持股这个状态再细分为：
//
// j=1表示当天卖出而不持股
// j=2表示当天没卖出，之前就没有股票了
// 整理一下dp[i][j]的状态：
//
// j=0: 第i天手上是有股票的。可能是第i天买入的，也可能是之前就已经有了。
// j=1: 第i天手上没有股票了。是因为第i天卖出才没有的。
// j=2: 第i天手上没有股票了，并且第i天没有卖出，是之前就没有了。
// 状态转移方程
// dp[i][0]:
// 昨天就有股票了，今天啥也不做。dp[i−1][0]
// 昨天没有股票且昨天没卖出，今天买入。dp[i−1][2]−prices[i]
// dp[i][1]:
// 昨天持有股票，今天卖出。dp[i−1][0]+prices[i]
// dp[i][2]:
// 昨天就没有股票，昨天也没卖出，今天啥也不做。dp[i−1][2]
// 昨天就没有股票，昨天卖出的，今天啥也不。dp[i−1][1]


public class MaxProfit {
    public static void main(String[] args) {
        int[] prices = {1,2,3,0,2};
        System.out.println(method2(prices));
    }

    //看题解后 自己写出的代码
    //暴力递归
    public static int method1(int[]price){
        return Math.max(process1(price,price.length-2,2),process1(price,price.length-2,0)+price[price.length-1]);
    }

    public static int process1(int[]price,int index,int action){
        if(index==0){
            if(action==1||action==2){
                return 0;
            }else{
                return -price[0];
            }
        }
        switch (action){
            case 0:
                return Math.max(process1(price,index-1,2)-price[index],process1(price,index-1,0));
            case 1:
                return process1(price,index-1,0)+price[index];
            case 2:
                return Math.max(process1(price,index-1,1),process1(price,index-1,2));
        }
        return 0;
    }

    //记忆化搜索
    public static int method2(int[]price){
        int n=price.length-1;
        int[][]dp=new int[price.length][3];
        dp[n][2]=process2(price,price.length-2,2,dp);
        dp[n][1]=process2(price,price.length-2,0,dp)+price[price.length-1];
        return Math.max(dp[n][2],dp[n][1]);
    }

    public static int process2(int[]price,int index,int action,int[][]dp){
        if(dp[index][action]!=0){
            return dp[index][action];
        }
        if(index==0){
            if(action==1||action==2){
                return 0;
            }else{
                return -price[0];
            }
        }
        switch (action){
            case 0:
                dp[index][action]=Math.max(process2(price,index-1,2,dp)-price[index],process2(price,index-1,0,dp));
                return dp[index][action];
            case 1:
                dp[index][action]=process2(price,index-1,0,dp)+price[index];
                return dp[index][action];
            case 2:
                dp[index][action]=Math.max(process2(price,index-1,1,dp),process2(price,index-1,2,dp));
                return dp[index][action];
        }
        return 0;
    }

    //严格表依赖
    public static int method3(int[]price){
        int n=price.length;
        int[][]dp=new int[n][3];
        dp[0][0]=-price[0];
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][2]-price[i],dp[i-1][0]);
            dp[i][1]=dp[i-1][0]+price[i];
            dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);
        }
        return Math.max(dp[n-1][2],dp[n-1][1]);
    }

}
